package com.heyqing;

/**
 * ClassName:MatrixChainOrder
 * Package:com.heyqing
 * Description:
 *
 * @Date:2024/6/21
 * @Author:Heyqing
 */
public class MatrixChainOrder {
    private int[][] m; // 保存最小乘法次数的表
    private int[][] s; // 保存最优解的决策点
    public MatrixChainOrder(int[] p) {
        int n = p.length - 1;
        m = new int[n][n];
        s = new int[n][n];

        for (int i = 0; i < n; i++) {
            m[i][i] = 0;
        }
        for (int l = 2; l <= n; l++) { // l表示矩阵链的长度
            for (int i = 0; i < n - l + 1; i++) {
                int j = i + l - 1;
                m[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
                    if (q < m[i][j]) {
                        m[i][j] = q;
                        s[i][j] = k;
                    }
                }
            }
        }
    }
    public void printOptimalParens(int i, int j) {
        if (i == j) {
            System.out.print("A" + (i+1));
        } else {
            System.out.print("(");
            printOptimalParens(i, s[i][j]);
            printOptimalParens(s[i][j]+1, j);
            System.out.print(")");
        }
    }
    public static void main(String[] args) {
        int[] dimensions = {40, 30, 20, 10, 5};
        MatrixChainOrder mcm = new MatrixChainOrder(dimensions);
        System.out.println("最少乘法次数: " + mcm.m[0][3]);
        System.out.println("组合方案:");
        mcm.printOptimalParens(0, 3);
    }
}